#include "../include/header.h"


// 数据结构定义


struct NODE {
    NODE* pLeft;
    NODE* pRight;
    int nMaxLeft;
    int nMaxRight;
    int nValue;
};

int nMaxLen = 0;
// Buliding a new node.
NODE* CreateTreeNode(int value)
{
    NODE* pNode = (NODE*)malloc(sizeof(NODE));
    pNode->nValue = value;
    pNode->pLeft = NULL;
    pNode->pRight = NULL;
    pNode->nMaxLeft = 0;
    pNode->nMaxRight = 0;
    return pNode;
}
//Construct a tree base on root.
void ConnectTreeNodes(NODE* pParent, NODE* pLeft, NODE* pRight)
{
    if(pParent != NULL) {
        pParent->pLeft = pLeft;
        pParent->pRight = pRight;
    }
}
// Printing a node in the tree.

void PrintTreeNode(NODE* pNode)
{
    if(pNode != NULL) {
        printf("value of this node is: %d\n", pNode->nValue);

        if(pNode->pLeft != NULL)
            printf("value of its left child is: %d.\n", pNode->pLeft->nValue);
        else
            printf("left child is null.\n");

        if(pNode->pRight != NULL)
            printf("value of its right child is: %d.\n", pNode->pRight->nValue);
        else
            printf("right child is null.\n");
    } else {
        printf("this node is null.\n");
    }

    printf("\n");
}

// Print the whole tree.
void PrintTree(NODE* pRoot)
{
    PrintTreeNode(pRoot);

    if(pRoot != NULL) {
        if(pRoot->pLeft != NULL)
            PrintTree(pRoot->pLeft);

        if(pRoot->pRight != NULL)
            PrintTree(pRoot->pRight);
    }
}

// Delete a whole tree.
void DestroyTree(NODE* pRoot)
{
    if(pRoot != NULL) {
        NODE* pLeft = pRoot->pLeft;
        NODE* pRight = pRoot->pRight;

        delete pRoot;
        pRoot = NULL;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}


// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
    //遍历到叶子节点，返回
    if(pRoot == NULL) {
        return;
    }
    // 如果左子树为空，那么该节点的左边最长距离为0
    if(pRoot -> pLeft == NULL) {
        pRoot -> nMaxLeft = 0;
    }

    //如果右子树为空，那么该节点的右边最长距离为0
    if(pRoot -> pRight == NULL) {
        pRoot -> nMaxRight = 0;
    }

    // 如果左子树不为空，递归寻找左子树最长距离
    if(pRoot -> pLeft != NULL) {
        FindMaxLen(pRoot -> pLeft);
    }

    // 如果右子树不为空，递归寻找右子树最长距离
    if(pRoot -> pRight != NULL) {
        FindMaxLen(pRoot -> pRight);
    }

    // 计算左子树最长节点距离
    if(pRoot -> pLeft != NULL) {
        int nTempMax = 0;
        if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) {
            nTempMax = pRoot -> pLeft -> nMaxLeft;
        } else {
            nTempMax = pRoot -> pLeft -> nMaxRight;
        }
        pRoot -> nMaxLeft = nTempMax + 1;
    }

    // 计算右子树最长节点距离
    if(pRoot -> pRight != NULL) {
        int nTempMax = 0;
        if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) {
            nTempMax = pRoot -> pRight -> nMaxLeft;
        } else {
            nTempMax = pRoot -> pRight -> nMaxRight;
        }
        pRoot -> nMaxRight = nTempMax + 1;
    }

    // 更新最长距离
    if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) {
        nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
    }
}
//            1
//          /  \
//         2    3
//             /  \
//            4    5
//           / \    \
//         6    7    8
//                     \
//                      9
//                        \
//                         10



void TestForEleven()
{
    NODE* node1 = CreateTreeNode(1);
    NODE* node2 = CreateTreeNode(2);
    NODE* node3 = CreateTreeNode(3);
    NODE* node4 = CreateTreeNode(4);
    NODE* node5 = CreateTreeNode(5);
    NODE* node6 = CreateTreeNode(6);
    NODE* node7 = CreateTreeNode(7);
    NODE* node8 = CreateTreeNode(8);
    NODE* node9 = CreateTreeNode(9);
    NODE* node10 = CreateTreeNode(10);

    ConnectTreeNodes(node1, node2, node3);
    ConnectTreeNodes(node3, node4, node5);
    ConnectTreeNodes(node4, node6, node7);
    ConnectTreeNodes(node5, NULL, node8);

    ConnectTreeNodes(node8, NULL, node9);
    ConnectTreeNodes(node9, NULL, node10);

    FindMaxLen(node1);
    DestroyTree(node1);
    cout << "the max length between two nodes is :" << nMaxLen << endl;
}


